import copy


def exist(board, word):  # 超时了
    n = len(board)
    m = len(board[0])
    mark = [[0 for i in range(m)] for j in range(n)]
    end = len(word)

    def start(x, y, p=0):
        if board[x][y] != word[p]:
            return False
        p += 1
        if p == end:
            return True
        r = False
        mark_[x][y] = 1
        for x_, y_ in [[x, y - 1], [x - 1, y], [x, y + 1], [x + 1, y]]:
            if 0 <= x_ < n and 0 <= y_ < m and mark_[x_][y_] != 1:
                r = r or start(x_, y_, p)
        return r

    for i in range(n):
        for j in range(m):
            if board[i][j] == word[0]:
                mark_ = copy.deepcopy(mark)
                if start(i, j) is True:
                    return True
    return False


def exist2(board, word):
    n = len(board)
    m = len(board[0])
    done = len(word) - 1

    def detect(x, y, p=0):
        if board[x][y] != word[p]: return False
        if p == done: return True
        cache, board[x][y] = board[x][y], "#"
        for x_, y_ in [[x, y - 1], [x - 1, y], [x, y + 1], [x + 1, y]]:
            if 0 <= x_ < n and 0 <= y_ < m and board[x_][y_] != "#":
                if detect(x_, y_, p + 1) is True:
                    return True
        board[x][y] = cache
        return False

    for i in range(n):
        for j in range(m):
            if board[i][j] == word[0]:
                if detect(i, j) is True:
                    return True
    return False


if __name__ == '__main__':
    board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]]
    word = "ABCCED"
    test_board = [["a"]]
    test_word = "ab"
    print(exist2(test_board, test_word))
